{
 "cells": [
  {
   "cell_type": "markdown",
   "id": "ada777f1",
   "metadata": {},
   "source": [
    "## 2. 回溯类问题/DFS类问题"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "83a20994",
   "metadata": {},
   "source": [
    "### 2.1 基本介绍\n",
    "- 定义\n",
    "1. 回溯法主要用于解决组合问题，回溯算法也叫试探法，它是一种系统地搜索问题的解的方法。\n",
    "2. 回溯算法的基本思想是：从一条路往前走，能进则进，不能进则退回来，换一条路再试。\n",
    "3. 回溯算法实际上一个类似枚举的搜索尝试过程，主要是在搜索尝试过程中寻找问题的解，当发现已不满足求解条件时，就“回溯”返回，尝试别的路径。\n",
    "\n",
    "### 2.2 基本试题\n",
    "- 全排列\n",
    "\n",
    "> https://leetcode-cn.com/problems/permutations/\n",
    "\n",
    "> 给定一个不含重复数字的数组 nums ，返回其 所有可能的全排列 。你可以 按任意顺序 返回答案。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 58,
   "id": "4c030422",
   "metadata": {
    "scrolled": true
   },
   "outputs": [
    {
     "name": "stdout",
     "output_type": "stream",
     "text": [
      "before enter: [1] [2, 3]\n",
      "before enter: [1, 2] [3]\n",
      "temp result: [[1, 2, 3]]\n",
      "before enter: [1, 3] [2]\n",
      "temp result: [[1, 2, 3], [1, 3, 2]]\n",
      "before enter: [2] [1, 3]\n",
      "before enter: [2, 1] [3]\n",
      "temp result: [[1, 2, 3], [1, 3, 2], [2, 1, 3]]\n",
      "before enter: [2, 3] [1]\n",
      "temp result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1]]\n",
      "before enter: [3] [1, 2]\n",
      "before enter: [3, 1] [2]\n",
      "temp result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2]]\n",
      "before enter: [3, 2] [1]\n",
      "temp result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]\n",
      "result: [[1, 2, 3], [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1]]\n"
     ]
    }
   ],
   "source": [
    "# given input：nums = [1,2,3]\n",
    "# output：[[1,2,3],[1,3,2],[2,1,3],[2,3,1],[3,1,2],[3,2,1]]\n",
    "import copy\n",
    "# save all the suitable cases\n",
    "result = []\n",
    "nums = [1, 2, 3]\n",
    "\n",
    "\n",
    "# 路径， 选择路径， 符合要求的长度\n",
    "def search_path(cur_path, select_path, path_len):\n",
    "    for item in select_path:\n",
    "        # 需要使用深度拷贝，来避免后续操作对原有值进行修改\n",
    "        new_select_path = copy.deepcopy(select_path)   \n",
    "        new_cur_path = copy.deepcopy(cur_path)          \n",
    "        new_cur_path.append(item)\n",
    "        new_select_path.remove(item)\n",
    "        \n",
    "        # 继续向下搜索的条件\n",
    "        if len(new_cur_path) != path_len:\n",
    "            print(\"before enter:\", new_cur_path, new_select_path)\n",
    "            search_path(new_cur_path, new_select_path, path_len)\n",
    "        else:\n",
    "            result.append(new_cur_path)\n",
    "            print(\"temp result:\", result)\n",
    "\n",
    "search_path([], nums, len(nums))\n",
    "# return result\n",
    "print(\"result:\", result)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 60,
   "id": "c2cbba16",
   "metadata": {},
   "outputs": [],
   "source": [
    "# 改进版实现方法：\n",
    "# 按回溯法的一般思路：\n",
    "# result = []\n",
    "# def backtrack(路径， 选择列表)：\n",
    "#     if 满足结束条件：\n",
    "#         result.add(路径)\n",
    "#         return\n",
    "\n",
    "#     for 选择 in 选择列表：\n",
    "#         做选择，即将一个选择项加到路径中\n",
    "#         backtrack(路径，选择列表)\n",
    "#         撤销选择，即从路径中去除选择项目，便于下一次循环选择加入其他选择项目\n",
    "# TODO: 待编码实现"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "70c54dcc",
   "metadata": {},
   "source": [
    "- N皇后问题\n",
    "\n",
    "> 1. 问题特点：搜索可能的组合情况，前一个位置确定后，第二个位置有多种路径/选择\n",
    "> 2. leetcode题目: https://leetcode-cn.com/problems/n-queens/"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 62,
   "id": "6dca5147",
   "metadata": {},
   "outputs": [],
   "source": [
    "# to be coded"
   ]
  },
  {
   "cell_type": "markdown",
   "id": "8f9af7fa",
   "metadata": {},
   "source": [
    "### 2.3 DFS相关试题\n",
    "\n",
    "|题目编号| 934 |1102| 531| 533| 337| 113|\n",
    "|---|---|---|---|---|---|---|\n",
    "|题目内容|[最短的桥](https://leetcode-cn.com/problems/shortest-bridge/)||||[打家劫舍](https://leetcode-cn.com/problems/house-robber-iii/)|[最短路径的和](https://leetcode-cn.com/problems/path-sum-ii/)|"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "id": "fe5a8467",
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "kernelspec": {
   "display_name": "Python 3 (ipykernel)",
   "language": "python",
   "name": "python3"
  },
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": "3.7.3"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 5
}
